from __future__ import print_function
from .compat import *
import os, tempfile, operator
import collections
from functools import reduce

class TransitionError (Exception) :
    pass

class StateError (Exception) :
    pass

def cached (method) :
    name = "_%s_cache_" % method.__name__
    def wrap (self, *largs, **kargs) :
        if not hasattr(self, name) :
            setattr(self, name, {})
        cache = getattr(self, name)
        key = (largs, tuple(sorted(kargs.items())))
        if key not in cache :
            cache[key] = method(self, *largs, **kargs)
        return cache[key]
    return wrap

def reset_caches (method) :
    def wrap (self, *largs, **kargs) :
        for name, obj in list(self.__class__.__dict__.items()) :
            if isinstance(obj, collections.Callable) and hasattr(self, "_%s_cache_" % name) :
                setattr(self, "_%s_cache_" % name, {})
        return method(self, *largs, **kargs)
    return wrap

class State :
    def __init__ (self, name, final=False) :
        self.name = name
        self.final = final
        self._trans = {}
    def __len__ (self) :
        return len(self._trans)
    def __eq__ (self, other) :
        return (self.final == other.final) and (self._trans == other._trans)
    def __ne__ (self, other) :
        return not (self == other)
    def __getitem__ (self, label) :
        try :
            return self._trans[label]
        except KeyError :
            return []
    def dict (self) :
        return self._trans
    def __iter__ (self) :
        result = []
        for key, states in list(self._trans.items()) :
            for s in states :
                result.append((key, s))
        return iter(result)
    def __contains__ (self, label, state=None) :
        if label in self._trans :
            if state is None :
                return True
            else :
                return state in self._trans[label]
        else :
            return False
    def remove (self, label, state=None) :
        if label not in self._trans :
            raise TransitionError("not found")
        elif (state is None) and (len(self[label]) != 1) :
            raise TransitionError("not found")
        elif state is None :
            del self._trans[label]
        elif state not in self[label] :
            raise TransitionError("not found")
        elif len(self[label]) == 1 :
            del self._trans[label]
        else :
            self[label].remove(state)
    def __setitem__ (self, label, state) :
        try :
            self.remove(label, state)
        except :
            pass
        try :
            self._trans[label].append(state)
        except :
            self._trans[label] = [state]
    def deterministic (self) :
        if "" in self._trans :
            return False
        else :
            for label in self._trans :
                if len(self._trans[label]) > 1 :
                    return False
            return True

class StatesClasses :
    def __init__ (self) :
        self._cls = {}
    def new (self, cls) :
        _cls = tuple(sorted(set(cls)))
        for state in _cls :
            self._cls[state] = _cls
    def __getitem__ (self, state) :
        return self._cls[state]
    def all (self) :
        return set([tuple(l) for l in list(self._cls.values())])
    def __contains__ (self, cls) :
        return cls in self.all()
    def __iter__ (self) :
        return iter(self.all())

class Automaton :
    def __init__ (self, name="A") :
        self._states = {}
        self.name = name
        self.start = None
        self._count = 0
    def __contains__ (self, state) :
        return state in self._states
    def __iter__ (self) :
        result = []
        for name, state in list(self._states.items()) :
            result.append((name, state))
        return iter(result)
    def deterministic (self) :
        for name, state in self :
            if not state.deterministic() :
                return False
        return True
    def _closure (self, state) :
        todo = set([state])
        result = set([state])
        while len(todo) > 0 :
            current = todo.pop()
            for next in self[current][""] :
                if next not in result :
                    todo.add(next)
                    result.add(next)
        return result
    _closure = cached(_closure)
    def closure (self, *states) :
        result = set()
        for state in states :
            result.update(self._closure(state))
        return tuple(sorted(result))
    closure = cached(closure)
    def alphabet (self) :
        result = set()
        for name, state in self :
            for label, next in state :
                result.add(label)
        return "".join(sorted(result))
    def __len__ (self) :
        return len(self._states)
    def __getitem__ (self, name) :
        try :
            return self._states[name]
        except :
            raise StateError("not found")
    def add_state (self, name=None, initial=None, final=False) :
        if name is None :
            name = self._count
            self._count += 1
            if initial is None :
                initial = True
        if name in self._states :
            raise StateError("duplicated")
        if initial :
            self.start = name
        self._states[name] = State(name, final)
    add_state = reset_caches(add_state)
    def add_transition (self, source, target, label) :
        _source = self[source]
        _target = self[target]
        _source[label] = target
    add_transition = reset_caches(add_transition)
    def match (self, word, state=None) :
        if state is None :
            state = self.start
        current = self.closure(state)
        for char in word :
            next = set()
            for c in current :
                for n in self[c][char] :
                    next.update(self.closure(n))
            current = next
        for c in current :
            if self[c].final :
                return True
        return False
    def path (self, word, state=None) :
        if state is None :
            state = self.start
        current = set([(s, tuple()) for s in self.closure(state)])
        for char in word :
            next = set()
            for c, p in current :
                for n in self[c][char] :
                    for s in self.closure(n) :
                        if s == n :
                            next.add((s, p+(c, char)))
                        else :
                            next.add((s, p+(c, char, n, "")))
            current = next
        for c, p in current :
            if self[c].final :
                return p + (c,)
        return None
    def __str__ (self) :
        lines = []
        for name, state in self :
            if (name == self.start) and (state.final) :
                lines.append("initial state: %s (final)" % str(name))
            elif name == self.start :
                lines.append("initial state: %s" % str(name))
            elif state.final :
                lines.append("state: %s (final)" % str(name))
            else :
                lines.append("state: %s" % str(name))
            for label, next in state :
                lines.append("  %s -> %s" % (label, next))
        return "\n".join(lines)
    def draw (self, name, format="png") :
        if format == "eps" :
            format = "ps"
        if format == "ps" :
            outfile = "%s.eps" % name
        else :
            outfile = "%s.%s" % (name, format)
        if format == "dot" :
            out = open(outfile, "w")
        else :
            out = open(outfile + ".dot", "w")
        print('digraph "(%s)" {' % self.name, file=out)
        for name, state in self :
            print('"n%s" [' % str(name), file=out)
            print('  label = "%s"' % str(name), file=out)
            if name == self.start :
                print('  shape = "rectangle"', file=out)
            elif len(str(name)) > 5 :
                print('  shape = "ellipse"', file=out)
            else :
                print('  shape = "circle"', file=out)
            if state.final :
                print('  style = "bold,dashed"', file=out)
            print("]", file=out)
            for label, next in state :
                print('"n%s" -> "n%s" [' % (str(name), str(next)), file=out)
                if label != "" :
                    print('  label = "%s"' % label, file=out)
                print("]", file=out)
        print("}", file=out)
        out.close()
        if format != "dot" :
            os.system("dot -T%s -o %s %s" % (format, outfile, out.name))
            os.system("rm -f %s.dot" % outfile)
    def determinize (self, verbose=False) :
        result = Automaton("det(%s)" % self.name)
        alphabet = self.alphabet()
        start = self.closure(self.start)
        result.add_state(start, initial=True,
                         final=True in [self[s].final for s in start])
        if verbose :
            print("initial state:", start)
        queue = [start]
        while len(queue) > 0 :
            current = queue.pop()
            for label in alphabet :
                new = set()
                for state in current :
                    for next in self[state][label] :
                        new.update(self.closure(next))
                new = tuple(sorted(new))
                if len(new) == 0 :
                    continue
                if verbose :
                    print(current, ">>%s>>" % label, new)
                if new not in result :
                    queue.append(new)
                    final = False
                    for state in new :
                        if self[state].final :
                            final = True
                            break
                    result.add_state(new, initial=False, final=final)
                    if verbose :
                        if final :
                            print("new final state:", new)
                        else :
                            print("new state:", new)
                result.add_transition(current, new, label)
        return result
    def renumber (self, verbose=False, first=0) :
        result = Automaton("ren(%s)" % self.name)
        new = {}
        num = first
        for name, state in self.sorted() :
            if verbose :
                print("rename %s to %s" % (name, num))
            new[name] = num
            result.add_state(num, initial=(self.start==name),
                             final=state.final)
            num += 1
        for name, state in self :
            for label, next in state :
                result.add_transition(new[name], new[next], label)
        return result
    def minimize (self, verbose=False) :
        alphabet = self.alphabet()
        result = Automaton("min(%s)" % self.name)
        cls = StatesClasses()
        rest, final = [], []
        for name, state in self :
            if state.final :
                final.append(name)
            else :
                rest.append(name)
        cls.new(rest)
        cls.new(final)
        if verbose :
            print("final:", tuple(sorted(final)))
            print("other:", tuple(sorted(rest)))
        queue = [c for c in cls if len(c) > 1]
        def target_class (state, label) :
            trans = self[state][label]
            if len(trans) == 0 :
                return None
            else :
                return cls[trans[0]]
        while len(queue) > 0 :
            current = queue.pop()
            for label in alphabet :
                target = target_class(current[0], label)
                one, two = [current[0]], []
                for name in current[1:] :
                    if target_class(name, label) == target :
                        one.append(name)
                    else :
                        two.append(name)
                if len(two) > 0 :
                    if verbose :
                        print("split %s on '%s' => %s + %s" % (tuple(sorted(current)),
                                                               label,
                                                               tuple(sorted(one)),
                                                               tuple(sorted(two))))
                    cls.new(one)
                    if len(one) > 1 :
                        queue.append(one)
                    cls.new(two)
                    if len(two) > 1 :
                        queue.append(two)
                    break
        for c in cls :
            final = False
            for name in c :
                if self[name].final :
                    final = True
                    break
            result.add_state(c, initial=(self.start in c), final=final)
        for name, state in result :
            done = set()
            source = self[name[0]]
            for label, next in source :
                if label in done :
                    continue
                done.add(label)
                result.add_transition(name, cls[next], label)
                if verbose :
                    print(name, ">>%s>>" % label, cls[next])
        return result
    def regexp (self, tostr=True) :
        dfa = self.determinize().minimize().renumber(first=1)
        from .regexps import Word, Empty, Any
        def lang (i, j, k) :
            if k == 0 :
                labels = []
                for l, s in dfa[i] :
                    if j == s :
                        labels.append(l)
                if len(labels) == 0 :
                    result = Empty()
                else :
                    chars = "".join([l for l in labels if len(l) == 1])
                    if len(chars) == 0 :
                        result = Empty()
                    elif len(chars) == 1 :
                        result = Word(chars)
                    else :
                        result = Any(chars)
                    for l in [l for l in labels if len(l) > 1] :
                        result = result | Word(l)
                if i == j :
                    return result | Word("")
                else :
                    return result
            else :
                return lang(i, j, k-1) | (lang(i, k, k-1)
                                          & lang(k, k, k-1).star()
                                          & lang(k, j, k-1))
        result = reduce(operator.or_, [lang(dfa.start, f, len(dfa))
                                       for f, s in dfa if s.final])
        if tostr :
            return str(result)
        else :
            return result
    def sorted (self) :
        todo = [self[self.start]]
        done = set([self.start])
        result = []
        while len(todo) > 0 :
            state = todo.pop(0)
            result.append((state.name, state))
            for symbol, states in sorted(state.dict().items()) :
                for s in sorted(states) :
                    if s not in done :
                        todo.append(self[s])
                        done.add(s)
        return tuple(result)
    def __eq__ (self, other) :
        s = self.determinize().minimize()
        o = other.determinize().minimize()
        if len(s) != len(o) :
            return False
        s, o = s.renumber(), o.renumber()
        for name, state in s :
            if state != o[name] :
                return False
        return True
